This application claims benefit of priority under 35 U.S.C. xc2xa7119 to Japanese Patent Application No. 1999-369353, filed on Dec. 27, 1999, and Japanese Patent Application No. 2000-387684, filed on Dec. 20, 2000, the entire contents of which are incorporated by reference therein.
The present invention relates generally to a method and system for estimating a motion vector. More specifically, the invention relates to a motion vector estimating method and system capable of searching a candidate motion vector of a picture element (pixel), which projects from a reference screen, with a precision of, e.g., half pixels, in a process for estimating a motion vector of a dynamic image, and a recording medium in which a motion vector estimating procedure has been recorded.
In general, a motion vector estimating system is used for compensating the motion of dynamic images and for compressing dynamic images. As systems which are often used for compressing dynamic images, there are MPEG1 and MPEG2 which are international standards having been standardized by MPEG (Moving Picture Experts Group). In MPEGs serving as these standards, a motion-compensated coding technique is used between temporally spaced screens in order to compress redundancy in a time direction. In this case, it is required to estimate motion vectors.
A typical motion vector estimation uses a technique for carrying out a block matching between a coded block on a coded image and a plurality of candidate blocks, which exist in a predetermined search area on a reference image and which have the same size as that of the coded block, and for determining a correlation between the blocks to use a displacement of a block having the highest correlation from the coded block, as a motion vector. The coded block means a block on the current image which is to be coded. The reference screen means the whole screen including a reference image. The candidate block means a block on a reference image to which reference is made when a motion vector of a certain coded block is estimated. The search area means a certain area in a reference screen including all of candidate blocks for a certain coded block.
In the block matching, the absolute value of the difference between pixels arranged at the same positions in two blocks is often calculated to be added with respect to pixels in the whole area of the blocks to be used as an index value indicative of the correlation. In this case, the correlation is high as the index value is small.
In a test model of MPEG2, it is recommended to use a precision of one pixel in the primary search and a precision of half pixels in the secondary search, as a precision of search of a motion vector. Usually, the original image is used as a reference image in the primary search, and a local decoded image, which is obtained by decoding image data coded in an encoder, is used as a reference image in the secondary search.
With respect to the processing of the edge of a reference screen during a motion vector estimation with a precision of one pixel, in a well-known motion vector estimating system, e.g., in a MPEG2 coding LSI (Large Scale Integrated-circuit) produced as a motion vector estimating system, a correction is carried out so that a search area does not project from the reference screen, i.e., an obtained motion vector is located within the reference screen, when a motion vector is estimated with a precision of one pixel in a certain coded block.
However, if a motion vector with a precision of one pixel in a certain coded block indicates the boundary of a reference screen, when a motion vector is estimated with a precision of half pixels using the motion vector with a precision of one pixel as the center of search, there is the possibility that a part of pixels in one or more candidate blocks in the search area project outwardly from the reference screen. For example, in FIG. 1 schematically showing the vicinity of the boundary of the reference screen, with respect to the uppermost leftmost one of candidate motion vectors with a precision of half pixels in an area 203, candidate blocks including the uppermost leftmost one as an upper left pixel correspond to an area, which is surrounded by a chain line in the figure, to include pixels outside of the reference screen.
In FIG. 1, a motion vector 201 with a precision of one pixel is position at the upper left corner of a screen edge of the reference screen. An area 204 projecting from the screen edge 202 of the reference screen exists in the area 203 of candidate motion vectors with a precision of half pixels in a case where the motion vector 201 is used as the center of search, and the candidate motion vectors in the area 204 can not be used for the operation of a motion vector estimation, so that only points in an area 205 among the candidate motion vectors with a precision of half pixels are actually used as candidate motion vectors.
The above described conventional coding LSI copes with such a case by carrying out the processing for estimating a candidate block including projecting pixels and excluding the estimated candidate block from the candidates for a motion vector estimation with a precision of half pixels.
In an image coding system disclosed in Japanese Patent Laid-Open No. 5-227525 filed by the applicant, there is provided means for controlling at least one of a search area in a secondary motion search and a motion vector estimation precision, in accordance with an area from which a motion vector estimated by a primary motion search is estimated in the search area, particularly as set forth in claim 5.
Also in the conventional motion vector estimating system, when the motion vector with a precision of one pixel indicates the boundary of the reference screen and when a part of the candidate blocks during the motion vector estimation with a precision of half pixels corresponding thereto project from the reference screen, the candidate blocks required for the motion vector estimation with a precision of half pixels can be searched by the above described two methods.
However, in the former prior art, the number of candidate motion vectors is smaller than that when all of the search area is located within the reference screen. For example, only four candidate motion vectors shown in the area 205 of the candidate motion vectors with a precision of half pixels in the area 203 shown in FIG. 3 are used as candidate motion vectors. Also when candidate blocks having the highest correlation exist just nearby the original search area on the reference screen, the candidate blocks are not located within objects to be estimated, so that there is a problem in that the estimation precision deteriorates in the motion vector estimation with a precision of half pixels obtained by the secondary motion estimation.
In the latter prior art, positions in the search area for primary motion vectors are used for controlling the search area during the secondary motion search, so that there is a problem in that it is not possible to determine whether the primary motion vector is positioned at the edge of the reference screen if position information in the above described search area on the reference screen is not obtained. In addition, when a hardware resource is used for calculating the correlation between coded blocks and candidate blocks, the construction of candidate blocks outwardly projecting from the reference screen is wasted, so that there is a problem in that the use efficiency of the hardware resource deteriorates.
It is therefore an object of the present invention to eliminate the aforementioned problems and to provide a motion vector estimating system and method capable of putting a search area, which is used when a motion vector estimation with a precision of half pixels is carried out, in a reference screen by adding a correction value when a motion vector of a pixel located at the edge of a reference screen is estimated, thereby improving the precision of estimation of a motion vector with a precision of half pixels.
It is another object of the present invention to provide a motion vector estimating system and method which sufficiently improves the precision of estimation of a motion vector by sufficiently ensuring a search area when a motion vector with a precision of half pixels is estimated, since the original image is used as a reference image even in the estimation of a motion vector with a precision of one pixel which is not more extremely precise than the estimation of a motion vector with a precision of half pixels.
In order to accomplish the aforementioned and other objects, a motion vector estimating method according to a first basic construction of the present invention, comprises the steps of: obtaining the correlation between a coded block occupying an optional area on a screen of a coded current image, and a plurality of candidate blocks which exist in a search area having an optional size on a screen of a reference image temporally different from the current image and which occupies the same area as that of the coded block; selecting a candidate block having the highest correlation from the plurality of candidate blocks to obtain a displacement at that time as a primary motion vector; determining a secondary search area on the basis of the primary motion vector to estimate a positional relationship between a plurality of secondary candidate blocks, which occupy the same area as that of the coded block existing in the determined secondary search area, or the primary motion vector and the reference screen to determine whether the secondary search area or the secondary candidate block is positioned outside of the boundary of the reference screen; correcting the position on the basis of the primary motion vector so that the secondary search area or the secondary candidate block is located inside of the boundary of the reference screen, when it is determined that a part of the secondary search area or secondary candidate block is positioned outside of the boundary; obtaining the correlation between the plurality of corrected secondary candidate blocks, which exist in the corrected secondary search area based on the motion vector, the position of which has been corrected, and which occupy the same area as that of the coded block, and the coded block; selecting a secondary candidate block having the highest correlation from the plurality of secondary candidate blocks to obtain a displacement at that time as a secondary motion vector; and obtaining a desired motion vector on the basis of the primary motion vector, the correction quantity and the secondary motion vector. Here, a corrected primary motion vector can be obtained by correcting the motion vector by the correction quantity.
In the motion vector estimating method according to the first basic construction of the present invention, the step of correcting the position on the basis of the primary motion vector may move the primary motion vector or the search area to the inside of the reference screen so that a projecting part of the search area for primary motion vectors or candidate block is located inside of the boundary of the reference screen when the projecting part projects outwardly from the boundary of the reference screen.
In the motion vector estimating method according to the first basic construction of the present invention, the step of correcting the position on the basis of the primary motion vector may move the primary motion vector or the search area to the inside of the reference screen by extending the search area or the candidate block inside of the reference screen by pixels corresponding to a projecting part of the search area for primary motion vectors or candidate block, and thereafter, by removing the projecting part, when the projecting part of the search area for primary motion vectors or candidate block projects outwardly from the boundary of the reference screen.
In the motion vector estimating method according to the first basic construction of the present invention, the primary motion vector may be obtained with a precision of one pixel, and the secondary motion vector or the desired motion vector may be obtained with a precision of half pixels.
The motion vector estimating method according to the first basic construction of the present invention may further comprise a step of variable-length-coding image data by utilizing the desired motion vector.
A motion vector estimating system according to a second basic construction of the present invention comprises: a primary motion vector estimating part for obtaining the correlation between a coded block occupying an optional area on a screen of a coded current image, and a plurality of candidate blocks which exist in a search area having an optional size on a screen of a reference image temporally different from the current image and which occupies the same area as that of the coded block, to select a candidate block having the highest correlation from the plurality of candidate blocks to obtain a displacement at that time as a primary motion vector; a primary motion vector position determining part for determining a secondary search area on the basis of the primary motion vector to estimate a positional relationship between a plurality of candidate blocks, which occupy the same area as that of the coded block existing in the determined secondary search area, or the primary motion vector and the reference screen to determine whether the secondary search area or the secondary candidate block is positioned outside of the boundary of the reference screen; a primary motion vector position correcting part for correcting the position on the basis of the primary motion vector so that the secondary search area or the secondary candidate block is located inside of the boundary of the reference screen, when it is determined that a part of the secondary search area or secondary candidate block is positioned outside of the boundary; a secondary motion vector estimating part for obtaining the correlation between the plurality of corrected secondary candidate blocks, which exist in the corrected secondary search area based on the motion vector, the position of which has been corrected, and which occupy the same area as that of the coded block, and the coded block, to select a secondary candidate block having the highest correlation from the plurality of secondary candidate blocks to obtain a displacement at that time as a secondary motion vector; and a desired motion vector estimating part for obtaining a desired motion vector on the basis of the primary motion vector, the correction quantity and the secondary motion vector.
In the motion vector estimating system according to the second basic construction of the present invention, the primary motion vector position correcting part may move the primary motion vector or the search area to the inside of the reference screen so that a projecting part of the search area for primary motion vectors or candidate block is located inside of the boundary of the reference screen when the projecting part projects outwardly from the boundary of the reference screen.
In the motion vector estimating system according to the second basic construction of the present invention, the primary motion vector position correcting part may move the primary motion vector or the search area to the inside of the reference screen by extending the search area or the candidate block inside of the reference screen by pixels corresponding to a projecting part of the search area for primary motion vectors or candidate block, and thereafter, by removing the projecting part, when the projecting part of the search area for primary motion vectors or candidate block projects outwardly from the boundary of the reference screen.
A computer program including motion vector estimating procedures according to a third basic construction of the present invention, comprise: a procedure for obtaining the correlation between a coded block occupying an optional area on a screen of a coded current image, and a plurality of candidate blocks which exist in a search area having an optional size on a screen of a reference image temporally different from the current image and which occupies the same area as that of the coded block; a procedure for selecting a candidate block having the highest correlation from the plurality of candidate blocks to obtain a displacement at that time as a primary motion vector; a procedure for determining a secondary search area on the basis of the primary motion vector to estimate a positional relationship between a plurality of candidate blocks, which occupy the same area as that of the coded block existing in the determined secondary search area, or the primary motion vector and the reference screen to determine whether the secondary search area or the secondary candidate block is positioned outside of the boundary of the reference screen; a procedure for correcting the position on the basis of the primary motion vector so that the secondary search area or the secondary candidate block is located inside of the boundary of the reference screen, when it is determined that a part of the secondary search area or secondary candidate block is positioned outside of the boundary; a procedure for obtaining the correlation between the plurality of corrected secondary candidate blocks, which exist in the corrected secondary search area based on the motion vector, the position of which has been corrected, and which occupy the same area as that of the coded block, and the coded block; a procedure for selecting a secondary candidate block having the highest correlation from the plurality of secondary candidate blocks to obtain a displacement at that time as a secondary motion vector; and a procedure for obtaining a desired motion vector on the basis of the primary motion vector, the correction quantity and the secondary motion vector.
In the above-described first through third basic constructions, there are described a motion vector estimation method, system and program in which the desired motion vector is obtained by using the primary and secondary motion vectors and respective moving (correction) quantities thereof. However, the present invention can be applied to entire motion vector estimation method, system and program in which a desired motion vector is obtained by using one through n (n is a positive and integer number) motion vector (vectors) and respective moving (correction) quantities thereof.
For example, even though the desired motion vector is obtained by the primary and secondary motion vectors in the first though third constructions, a desired motion vector may be obtained as follows:
At first, a secondary motion vector is obtained from a primary motion vector and primary correction quantity, a tertiary motion vector is second obtained from the secondary motion vector and secondary correction quantity in the same manner as that of the secondary motion vector, . . . , an i motion vector (1 less than i less than =n) is obtained from an (ixe2x88x921)-th motion vector and (ixe2x88x921)-th correction quantity in the same manner as that of the former motion vector, . . . , and an n motion vector is obtained from an (nxe2x88x921)-th motion vector and (nxe2x88x921)-th correction quantity in the same manner as that of the former motion vector. Finally, a desired motion vector is obtained from the primary through (nxe2x88x921)-th motion vectors, the primary through (nxe2x88x921)-th correction quantity and the n-th motion vector.